<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->


<title>Maximum Sum</title>
<meta name="description" content="Maximum Sum">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<link rel="STYLESHEET" href="acm-00108_archivos/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">
 <h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font size="5" color="#c0ffff">&nbsp;<a name="SECTION0001000000000000000000">Maximum Sum</a></font>&nbsp;</b></td></tr></tbody></table></center></h1>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">Background</a></font></h2>
<p>
A problem that is simple to solve in one dimension is often much more
difficult to solve in more than one dimension.  Consider satisfying a
boolean expression in conjunctive normal form in which each conjunct
consists of exactly 3 disjuncts.  This problem (3-SAT) is NP-complete.
The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class
regardless of the dimensionality of the problem.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">The Problem</a></font></h2>
<p>
Given a 2-dimensional array of positive and negative integers, find
the sub-rectangle with the largest sum.  The sum of a rectangle is the
sum of all the elements in that rectangle.  In this problem the
sub-rectangle with the largest sum is referred to as the <em>maximal
sub-rectangle</em>. A sub-rectangle is any contiguous
sub-array of size  <img alt="tex2html_wrap_inline33" src="acm-00108_archivos/108img1.gif" align="middle" height="24" width="37">  or greater located within the
whole array. As an example, the maximal sub-rectangle of the array:
</p><p> <img alt="displaymath35" src="acm-00108_archivos/108img2.gif" align="bottom" height="78" width="322"> </p><p>
</p><p>
is in the lower-left-hand corner:
</p><p> <img alt="displaymath37" src="acm-00108_archivos/108img3.gif" align="bottom" height="56" width="274"> </p><p>
</p><p>
and has the sum of 15.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">Input and Output</a></font></h2>
<p>
The input consists of an  <img alt="tex2html_wrap_inline39" src="acm-00108_archivos/108img4.gif" align="middle" height="24" width="52">  array of integers.
The input begins with a single positive integer <i>N</i> on a line by itself
indicating the size of the square two dimensional array.  This is
followed by  <img alt="tex2html_wrap_inline43" src="acm-00108_archivos/108img5.gif" align="bottom" height="14" width="21">  integers separated by white-space (newlines and
spaces).  These  <img alt="tex2html_wrap_inline43" src="acm-00108_archivos/108img5.gif" align="bottom" height="14" width="21">  integers make up the array in row-major order
(i.e., all numbers on the first row, left-to-right, then all numbers on
the second row, left-to-right, etc.).  <i>N</i> may be as large as 100.  The
numbers in the array will be in the range [-127, 127].
</p><p>
</p><p>
The output is the sum of the maximal sub-rectangle.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">Sample Input</a></font></h2>
<p>
</p><pre>4
0 -2 -7  0 9  2 -6  2
-4  1 -4  1 -1
8  0 -2</pre>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001005000000000000000">Sample Output</a></font></h2>
<p>
</p><pre>15</pre>
<p>
</p></body></html>